package wh.最长公共前缀;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/3/23 21:33
 * @description:编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
 * @version: 1.0
 */
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        //从数组中的第二个字符串开始比较,在上一组的公共前后缀作为参数1，和下一个数组进行比较，得出一个新的公共前后缀，
        // 一但prefix为空，说明不存在整个数组的公共前后缀，立刻退出返回空字符串。
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    //返回字符串str1,和字符串str2的最长公共前后缀
    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }


    //解法2
    public String longestCommonPrefix2(String[] strs) {
        if(strs.length == 0)
            return "";
        //假设最长公共缀为第一个字符串
        String ans = strs[0];
        //通过for循环，与后续字符串比较。不断筛选前后缀
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                //一旦字符串不同，立刻退出for循环。得到一个j
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            //j为0，说明公共前后缀为空字符串
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }


}

